package com.da.javatest.niuke.baodian;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * @author chenlida
 * @date 2020/10/11 22:17
 * https://www.nowcoder.com/practice/764edc8f2a6147429a098f422753853b?tpId=8&tags=&title=&diffculty=0&judgeStatus=0&rp=1
 */
public class C53SortString {
    public ArrayList<String> sortStrings(String[] str, int n) {
        Set<String> set = new HashSet<>();
        for (String s : str) {
            set.add(sort(s));
        }
        return (ArrayList<String>)set.stream().sorted().collect(Collectors.toList());
    }

    private String sort(String str) {
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        return new String(chars);
    }

    public ArrayList<String> sortStrings2(String[] str, int n) {
        Map<String, String> map = new HashMap<>();

        for (int i = 0; i < n; i++) {  //找出所有变位词
            char[] chars = str[i].toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            String value = map.get(key);
            if (value == null || value.compareTo(str[i]) > 0)  //字典排序选变位词
            {
                map.put(key, str[i]);
            }
        }
        ArrayList<String> list = new ArrayList<>(map.values());
        Collections.sort(list); //所有变位词排序
        return list;
    }

    public static void main(String[] args) {
        C53SortString test = new C53SortString();
        System.out.println(test.sort("dbac"));
        System.out.println(test.sortStrings(new String[] {"ab", "ba", "abc", "cba"}, 3));
        System.out.println(test.sortStrings2(new String[] {"ab", "ba", "abc", "cba"}, 3));
    }
}
